
# 相交链表


class ListNode:
    def __init__(self, x, next=None):
        self.val = x
        self.next = next


# 构建一个列表
def build_linked_list(arr: list) -> ListNode:
    if not arr:
        return
    
    head = ListNode(arr[0])
    curr = head
    for val in arr[1: ]:
        curr.next = ListNode(val)
        curr = curr.next  
    return head


class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        p, q = headA, headB
        while p != q:
            # print(type(q))
            # print(p.val)
            # print(q.val)
            if p:
                p = p.next
                
            else:
                p = headB
            
            if q:
                q = q.next
            else:
                q = headA
                
        
        return p





if __name__ == "__main__":

    arrA = [4, 1, 8, 4, 5]
    arrB = [5, 6, 1, 8, 4, 5]
    # 这一部分有问题，构造出了两个值相同，但是物理内存不同的链表
    headA = build_linked_list(arrA)
    headB = build_linked_list(arrB)

    sol = Solution()
    res = sol.getIntersectionNode(headA, headB)

    print(res)

